#include <stdio.h>
#include<iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
//打印数组
void print_arr(int* arr, int n) {
    int i;
    printf("%d", arr[0]);
    for (i = 1; i < n; i++)
        printf(" %d", arr[i]);
    printf("\n");
}

void counting_sort(int* start_arr, int* sorted_Arr, int n) {
    int* count_arr = (int*)malloc(sizeof(int) * 100);//申请临时的数组
    for (int k = 0; k < 100; k++)//将临时数组的元素值置为零
        count_arr[k] = 0;
    for (int i = 0; i < n; i++)//统计各个元素出现的次数
        count_arr[start_arr[i]]++;
    for (int k = 1; k < 100; k++)//对所有计数进行累加
        count_arr[k] += count_arr[k - 1];
    for (int j = n; j > 0; j--)//将临时数组的值赋值到原数组
        sorted_Arr[--count_arr[start_arr[j - 1]]] = start_arr[j - 1];
    free(count_arr);
}


int Ksearch(int arr[], int n, int K, int& Index)
{
    if (K<0 && K>n)//非法输入
    {
        return 0;
    }

    Index = arr[n - K];//寻找第K大元素
    return Index;
}


int main() {
    int n = 10;//数组的大小
    int* arr = (int*)malloc(sizeof(int) * n);//申请数组空间
    int* sorted_Arr = (int*)malloc(sizeof(int) * n);

    //给原数组随机赋值
    srand(time(0));
    for (int i = 0; i < n; i++)
        arr[i] = rand() % 100;
    printf("待排序的数组: ");
    print_arr(arr, n);

    //计数排序后的数组
    counting_sort(arr, sorted_Arr, n);
    printf("排序后的数组: ");
    print_arr(sorted_Arr, n);

    /*int Index = 0;
    int K;
    cout << "请输入K的值: ";
    cin >> K;
    cout << "第" << K << "大元素是: ";
    cout << Ksearch(sorted_Arr, n, K, Index);*/
    //销毁数组，释放空间
    free(arr);
    free(sorted_Arr);
    return 0;
}